14 I ELEMENTS OF THE THEORY OF SETS

Let ji-*•<*, be a bijection of N onto A; then n-+f(an) is a mapping
of N onto B, and we can therefore suppose A = N. For each b e B, f~l(b)
is not empty by assumption; let m(b) be its smallest element. Then/(/n(6)) = *,
which shows at once that m is an injective mapping of B into N; m can be
considered as a bijection of B onto m(B) <= N, and by (1.9.1) m(S) is at most
denumerable. Q.E.D.

We observe that if a set A is at most denumerable, there is always a
surjection of N onto A; this is obvious if A is infinite; if not, there is a bijection
/of an interval Q^f^m onto A, and one extends/to a surjection by putting
g(n) =/(w) for n > m.

(1.9.3) The set N x N = N2 is denumerable.

We define an injection / of N x N into N by putting

("diagonal enumeration"; it turns out to be a bijection, but we do not need
that result). Indeed, ifx + y=*a, then (a +l)(a + 2)/2 = a + I + a(a + l)/2;
hence if x + y < x' + /, as y^a, f(x, y)^a + a(a + l)/2 </(*', /) ; and
if x + j = *' + / and / < j,/(x, y) - /(*', /) = y - / ; hence (x, y) ^ (xf, y')
implies f(x9y) ^f(x',y'). We then apply (1.9.1).

We say that a family (x^)^et is denumerable (resp. <atf mc?^^ denumerable)
if the set of indices L is denumerable (resp. at most denumerable).

(1 .9.4) The union of a denumerable family of denumerable sets is denumerable.

Let (AJ^L be a denumerable family of denumerable sets; there is a
bijection n -» An of N onto L, and for each 1 e L, a bijection n ->/A(w) of N
onto AA . Let A = (j AA , and consider the mapping (m, n) -»/An(w) of

A 6 1^

N x N into A; this mapping is surjective, for if x e AM , there is an n such
that 11 = ln, and an m such that x =/M(w) =f^n(m). The result now follows
from (1.9.3) and (1.9.2) since A is infinite.

The result (1.9.4) is still valid if the word "denumerable" is everywhere
replaced by "at most denumerable." We have only to replace bijections by
surjections in the proof, using the remark which follows (1 .9.2).

Finally, we consider the following result as an axiom:
(1 .9.5) Every infinite set contains a denumerable subset.s finite